package 哈希表;

import java.util.HashMap;
import java.util.Map;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/3 17:28
 */
public class lc525连续子数组0And1相等 {


    /*
     思想 为 lc560 的 a - b = k 版本
     */
    public int findMaxLength2(int[] nums) {
        int sum = 0, max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            if (sum == 0) {
                max = Math.max(max, i + 1);
            }
            if (map.containsKey(sum - 0)) {
                max = Math.max(max, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }


        return max;
    }


    /*
     给出一个 数组, nums[], 里面全是二进制 01
     请找除 ,0 和 1元素个数相等的 连续子数组的个数!
     - 将题目进行转化一下, 话, 又变成 了 ,枚举 末端点 + 哈希表的 类型了!
     */
    public int solution(int nums[]) {
        int ans = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>(nums.length);

        map.put(0, -1); // 这里 是 -1, 主要一下, 这里 的 value 是 下标,要注意这一点! 相当于 一个 哨兵的作用!


        // 直接 写个最 简洁的版本吧
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(sum)) { // 当前 sum = 0, 并且 map 缓存的 之前也出现过 0
                ans = Math.max(ans, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return ans;
    }


    /*
     * 令01前缀和为0，1之和的前缀和，它遇到0会-1，遇到1会+1
     * 若子数组[i,j]的01前缀和满足 sum[j] - sum[i - 1] = 0
     * 说明[i,j]中的0，1数量相同
     *      使用 cnt 统计 0，1 之和(遇到0会-1，遇到1会+1)；map 统计 某cnt 的最早出现的下标位置
     *      设 某个cnt 最早出现的位置在 pioneer， 当前读取的位置为 cur
     *          1.当 cnt 已经存在 map 中，则0，1相同的长度为 cur - pioneer
     *          2.当 cnt 不存在 map，则说明这个统计是个 pioneer，使其存储在 map 中
     *      取其中最长的 cur - pioneer
     *  初始情况cnt为0，它的位置在-1
     */
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        int cnt = 0;
        int res = 0;
        map.put(cnt, -1);
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                cnt++;
            } else {
                cnt--;
            }

            if (map.containsKey(cnt)) {
                res = Math.max(res, i - map.get(cnt));
            } else {
                map.put(cnt, i);
            }
        }
        return res;
    }




}
